
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM55 没有重复项数字的全排列
 * <a href="https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=295&tqId=701&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-02-26
 * Time: 23:42
 */
//这道题牛客答案有错，这个是牛客答案的解法，无法做到按字节序升序输出，如果非要按照字节序输出，则需要将res数组重新排序
public class Solution {
    private void swap(ArrayList<Integer> list, int i, int j) {
        Integer temp = list.get(i);
        list.set(i,list.get(j));
        list.set(j,temp);
    }
    private void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index) {
        int size = num.size();
        if (index == size - 1) {
            res.add(new ArrayList<>(num)); //这里切不可写成res.add(num)
        } else {
            for (int i = index; i < size; i++) {
                swap(num,index,i);
                recursion(res,num,index + 1);
                swap(num,index,i);
            }
        }
    }
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        //1.先将数组排序为升序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> nums = new ArrayList<>();
        //数组转ArrayList
        for (int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }
        recursion(res,nums,0);
        return res;
    }

    public static void main(String[] args) {
        int[] num = {1, 2, 3};
        Solution solution = new Solution();
        ArrayList<ArrayList<Integer>> res = solution.permute(num);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }
}
